1. Field of the Invention
The present invention relates to the technical field of cryptography and the present invention particularly refers to the detection of so called fault attacks of cryptographic units.
2. Description of the Related Art
So-called fault attacks (FA) represent a serious threat for the implementation of cryptographic algorithms, irrespective of whether the algorithm is implemented in software or as hardware module.
While asymmetric methods, such as RSA, may be protected in a relatively simple way by well-known published measures, it is extremely difficult to protect symmetric encryption methods, such as the advanced encryption standard (AES) or the DES (data encryption standard). With simple technical means, an attacker is capable of disturbing the algorithm during the processing so that, for example, internal intermediate results (for example round keys or intermediate results of rounds) comprise one bit faults or multiple bit faults. These faults result in wrong encryption or decryption results. In a cryptographic analysis, the secret key may be calculated from only a small number of such results. For this, it is not even necessary to inject the bit faults at specific positions.
According to a publication by Giraud (“Differential Fault Analysis On AES”, Eprint IACR 2003-008, http://eprint. iacr.org/2003/008.ps), as little as 50 wrong results are sufficient for one bit faults in intermediate results of the ninth round of AES 128, or about 250 wrong results are sufficient for byte faults in round keys of the eighth or ninth round or in intermediate results of the ninth round.
In the case of one bit faults, an efficient method of online fault detection is known (see for example Wu, Karri, Kusnetsov, Gössel, Low Cost Concurrent Error Detection for the Advanced Encryption Standard, Preprint 0 08/2003, Oct. 2003, ISSN 0946-7580, University of Potsdam, or Gössel, German Patent Application DE 10261810.0: “Verfahren zur Fehlererkennung beim kryptographischen Transformieren von binären Daten und Schaltungsanordnung”; or Bretoni, Breveglieri, Korem, Piuri, “On the propagation of faults and their detection in a hardware implementation of the advanced encryption standard”, Proc. ASAP'02, pp. 303-312, 2002). If, however, a higher security level is necessary, the occurrence of any multiple bit faults has to be detected. Thus, there are no general solutions known today for the case of injected multiple bit faults except trivial redundancy as:                a) multiple repetition of the encryption (or decryption) and comparison of the results (time redundancy).                    The latter may also be implemented for example as an encryption with subsequent decryption and comparison of the result with the output data for making the attack more difficult. In any case, this method results approximately in halving the data throughput. In order to diminish this disadvantage, only the last or the last two rounds may be calculated (or calculated back) repeatedly, for example, because in this attack (for example according to the above publication by Giraud from the year 2003) faults in these rounds may be used. However, one cannot rule out in this case that more sophisticated cryptographic analysis methods may be successful even here.                        b) Multiple implementation with comparison of the results (information redundancy).                    However, the double implementation, for example, requires a high hardware effort and still contains security gaps, because in this case the comparison may, for example, also be a target of the attack. If injected faults in the comparator lead to the non-detection of the inequality of results, a wrong result may still be output. Furthermore, the identical duplication and the comparison have the weakness that the probability for “equal faults” in both data paths is not negligible and thus sufficiently faulty results are not detected and a successful attack becomes possible.                        
Fault detection in the AES algorithm may also be done, for example, by parity bits, which is, for example, known from the above publication by Bretoni et al. or Wu et al.
The fault detection by parity bits has the disadvantage that only an uneven number of faulty bits for which the parity is determined can be detected. As already mentioned, the basically simplest method for fault detection, which is well known to someone skilled in the art, is the duplication and comparison. By duplication and comparison, all faults are detected which involve either only the circuit to be monitored, the duplicated circuit or only the comparator. However, the effort for the duplication and the comparison is high.
FIG. 6 shows a circuit S 31 having m=4 binary inputs x=X1, X2, X3, x4 and n=4 binary outputs y=Y1, Y2, Y3, Y4, which is duplicated into the circuit S1=S 32 having the m=4 inputs x=X1, X2, X3, X4 and the n=4 outputs Y=Y1, Y2, Y3, Y4. The outputs of the circuits S and S1 are compared in the comparator COMP 33 having 2n=8 inputs and two outputs f1, and f2. If there is no fault, the comparator COMP 33 outputs the values 0,1 or 1,0 at its outputs f1, f2. If there is a fault in one of the circuits S, S2 or in the comparator COMP 33, the comparator COMP 33 outputs the values 0,0 or 1,1 at its outputs f1 and f2.
There are special features for the fault detection by duplication and comparison for cryptographic circuits serving to transform unencrypted data to encrypted data or to transform encrypted data to unencrypted data. First, as in other circuits as well, technical faults, such as stuck-at faults and other technical faults, are to be detected by duplication and comparison. However, faults are also injected deliberately into cryptographic circuits to be able to draw conclusions as to the method of encryption based on the then faulty outputs of the circuits and to be able to determine, for example, the used cryptographic key. If, for example, two faults of the same kind are injected into the original circuit and into the duplicated circuit, these errors cannot be detected by duplication and comparison. The possibility to inject equal faults into the original circuit and into the duplicated circuit is facilitated if both circuits are constructed in the same way, which is disadvantageous. If a self-checking comparator is used for the comparison of the circuit outputs, which is normally made of a self-checking two-rail checker with inverted inputs, as is known to someone skilled in the art (and is furthermore described, for example, in Wakerly, J. Error Detecting Codes, Self-Checking Circuits and Applications, New York, 1978), a relatively large percentage of the faults injected into the circuit to be monitored cannot be detected by duplication and comparison in a relatively simple manner by simultaneously injecting faults into the comparator and into the circuit to be monitored, which is also disadvantageous. As faults in cryptographic circuits are normally injected stochastically, for example by irradiating the circuit, this results in a relatively high probability that faults in the circuit to be monitored are not detected and the faulty outputs may be analyzed. A completely self-checking comparator is usefully constructed as a completely self-checking two-rail checker with inverted inputs.
According to prior art, a completely self-checking two-rail checker is designed as a tree structure of two-rail checker cells TRCZ 48 having four inputs a1, a′1, b1, b′1 and two outputs e1, e′1, as illustrated in FIGS. 7A and 7B, as known to someone skilled in the art, and furthermore illustrated, for example, in Wakerly, J. Error Detecting Codes, Self-Checking Circuits and Applications, New York, 1978. A two-rail checker cell is a two-rail checker having four inputs and two outputs. It consists of four AND gates 41, 42, 43, and 44 and two OR gates 45 and 46 whose outputs e1 and e′1 are the outputs of the two-rail checker cell. Its four inputs are designated a1, a′1, b1, b′1.
If the two-rail checker cell TRCZ of FIG. 7B is faultless, each two-rail input a1, a′1, b1, b′1 =a1, ā1, a2, ā2 always causes a two-rail output e1, e′1 =e1, ē1, and each non-two-rail input results in a non-two-rail output e1, e′1=e1, e1.
If any input or an output of a gate of the two-rail checker cell TRCZ is “stuck at” 0 or “stuck at” 1, so that a constant value of 0 or 1 is applied to this input and/or output in a faulty way, there is a correct two-rail input so that the output is non-two rail. If, for example, the input line of the AND gate 41 in FIG. 4 marked 47 is “stuck at” 1, the two-rail checker cell TRCZ outputs the value e1, e′1=1, 1 for an input of 0, 1, 1, 0, and since the output 1, 1 is non-two rail, the fault is detected.
However, it is noted that, for the input of the faulty input 0, 0, 1, 0, the considered fault “stuck at” 1 and the considered faulty input are not detected, because, for this input, the two-rail checker cell TRCZ outputs the two-rail value 1, 0, so that the faulty input 0, 0, 1, 0 is masked by the “stuck at” 1 fault on the line marked 47 in FIG. 7A. The same fault “stuck at” 1 of the two-rail checker cell of FIG. 7A for example also masks the faulty input 0, 0, 1, 1. A completely self-checking two-rail checker TRC is designed as a tree structure of two-rail checker cells TRCZ, as illustrated in FIG. 8 for a two-rail checker having eight inputs and two outputs f1, and f2 carrying the fault signal. The two-rail checker having eight inputs and two outputs is structured as a tree of the three two-rail checker cells 51, 52 and 53 by directing the outputs of the two-rail checker cells 51 and 52, which are two bits wide each, into the four bit wide input of the two-rail checker cell 53, whose two bit wide output is the output of the two-rail checker 54 carrying the fault signal f2. The two inputs of the two-rail checker cells 51 and 52, which are four bits wide each, form the eight bit wide input of the two-rail checker 54.
If, for example, a fault is deliberately injected into the circuit realizing the two-rail checker, for example into the two-rail checker cell TRCZ 53 which is directly connected to the outputs of the two-rail checker, and simultaneously into the circuit S in FIG. 8, there is a relatively high percentage of faults of the circuits S which have the effect of faults at the inputs of the two-rail checker TRC as non-two-rail signals, but which cannot be detected as errors due to the now simultaneously faulty two-rail checker, which is disadvantageous particularly for cryptographic circuits. The faulty data at the outputs of the circuit S cannot be turned off then and are available for evaluation, for example for the determination of the key of the cryptographic circuit.
Further prior art regarding fault attacks is known from the following fundamental publications:
E. Biham, A. Shamir, “Differential Fault Analysis of Secret Key Cryptosystems”, Springer Lecture Notes in Computer Science, vol. 1294, Advances in Cryptology, Proceedings of CRYPTO'97, pp. 513-525, 1997.